package code;
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.io.*;
import java.util.*;

import learn.*;


/**
 *
 * @author jyotesh
 */
public class MPA {
    
    private boolean[][] graph = null;
    private int[] arity = null;
    private ArrayList<ArrayList<Integer>> cliques = null;
    private int[][] junctionTree = null;
    private HashMap<ArrayListWrapper, HashMap<CliqueWrapper, Double>> potentials = null;
    private HashMap<Integer, HashMap<CliqueWrapper, Double>> cliquePotentials = null;
    private ArrayList<HashMap<CliqueWrapper, Double>> messageList = new ArrayList<HashMap<CliqueWrapper, Double>>();
    private int[][] messageIndex = null;
    private ArrayList<ArrayList<Integer>> separatorList = new ArrayList<ArrayList<Integer>>();
    private int[][] separatorIndex = null;
    private ArrayList<HashMap<CliqueWrapper, Double>> maxMessageList = new ArrayList<HashMap<CliqueWrapper, Double>>();
    private ArrayList<HashMap<CliqueWrapper, HashMap<Integer, Integer>>> maxMessageAssignment = new ArrayList<HashMap<CliqueWrapper, HashMap<Integer, Integer>>>();
    private HashMap<CliqueWrapper, Double> marginal = new HashMap<CliqueWrapper, Double>();
    private ArrayList<Integer> variables = new ArrayList<Integer>();
    private HashMap<Integer, Integer> finalAssignment = new HashMap<Integer, Integer>();
    private int e, n;
    private double finalPotential;

    public MPA() {
        readGraph("./learnstructure.txt");
        readPotentials("./learnpotential.txt");
        triangulate();
        createJT();
        createAlpha();
        computeMessages();
    }
    
    private void readGraph(String fileName) {
        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(fileName));
            StringTokenizer st = null;
            String line;
            int node1, node2, nodeIndex;
            line = br.readLine();
            n = Integer.parseInt(line);
            line = br.readLine();
            e = Integer.parseInt(line);
            arity = new int[n];
            for (int i = 0; i < n; i++) {
                line = br.readLine();
                st = new StringTokenizer(line);
                nodeIndex = Integer.parseInt(st.nextToken());
                arity[nodeIndex] = Integer.parseInt(st.nextToken());
            }
            graph = new boolean[n][n];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    graph[i][j] = false;
            for (int i = 0; i < e; i++) {
                line = br.readLine();
                st = new StringTokenizer(line);
                node1 = Integer.parseInt(st.nextToken());
                node2 = Integer.parseInt(st.nextToken());
                graph[node1][node2] = graph[node2][node1] = true;
            }
        }
        catch(FileNotFoundException fe) {
            System.out.println("File not found: " + fileName);
        }
        catch(IOException ie) {
            System.out.println("Error reading file " + fileName);
        }
        finally {
            try {
                if(br != null)
                    br.close();
            }
            catch(IOException ie) {
                System.out.println("Error closing file " + fileName);
            }
        }
    }
    
    private void readPotentials(String fileName) {
        BufferedReader br = null;
        try {
            br = new BufferedReader(new FileReader(fileName));
            StringTokenizer st = null;
            String line;
            int length;
            potentials = new HashMap<ArrayListWrapper, HashMap<CliqueWrapper, Double>>();
            while ((line = br.readLine()) != null) {
                st = new StringTokenizer(line);
                ArrayListWrapper cliqueNodeList = new ArrayListWrapper();
                st.nextToken();
                while (st.hasMoreTokens())
                    cliqueNodeList.add(Integer.parseInt(st.nextToken()));
                length = 1;
                for (int i = 0; i < cliqueNodeList.size(); i++)
                    length *= arity[cliqueNodeList.get(i)];
                HashMap<CliqueWrapper, Double> factorPotentials = new HashMap<CliqueWrapper, Double>();
                for (int i = 0; i < length; i++) {
                    line = br.readLine();
                    st = new StringTokenizer(line);
                    CliqueWrapper potential = new CliqueWrapper(arity, cliqueNodeList);
                    for (int j = 0; j < cliqueNodeList.size(); j++)
                        potential.add(Integer.parseInt(st.nextToken()));
                    factorPotentials.put(potential, Double.parseDouble(st.nextToken()));
                }
                potentials.put(cliqueNodeList, factorPotentials);
            }
        }
        catch(FileNotFoundException fe) {
            System.out.println("File not found: " + fileName);
        }
        catch(IOException ie) {
            System.out.println("Error reading file " + fileName);
        }
        finally {
            try {
                if(br != null)
                    br.close();
            }
            catch(IOException ie) {
                System.out.println("Error closing file " + fileName);
            }
        }
    }
    
    private void display() {
        System.out.println("Number of nodes = " + n);
        System.out.println("Number of edges = " + e);
        System.out.println("Arity Array");
        for (int i = 0; i < n; i++)
            System.out.println("NodeIndex = " + i + " Arity = " + arity[i]);
        System.out.println("Adjacency Matrix");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                System.out.print(graph[i][j] + " ");
            System.out.println();
        }
        System.out.println("Potentials");
        Iterator potentialsIterator = potentials.keySet().iterator();
        while (potentialsIterator.hasNext()) {            
            ArrayListWrapper arrayListKey = (ArrayListWrapper)potentialsIterator.next();
            System.out.println(arrayListKey.toString() + " => ");
            HashMap<CliqueWrapper, Double> value = (HashMap<CliqueWrapper, Double>)potentials.get(arrayListKey);
            Iterator cliqueIterator = value.keySet().iterator();
            while (cliqueIterator.hasNext()) {
                CliqueWrapper cliqueKey = (CliqueWrapper)cliqueIterator.next();
                System.out.println(cliqueKey.toString() + " => " + (Double)value.get(cliqueKey));
            }
        }
    }
    
    private void triangulate() {
        NodeList nodeList = new NodeList(graph);
        //nodeList.displayData();
        int[] indexList = nodeList.getIndexList();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++)
            visited[i] = false;
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> neighbours = new ArrayList<Integer>();
            for (int j = 0; j < n; j++)
                if (graph[indexList[i]][j])
                    neighbours.add(j);
            int length = neighbours.size();
            for (int j = 0; j < length; j++)
                if (!visited[neighbours.get(j)])
                    for (int k = j + 1; k < length; k++)
                        if (!visited[neighbours.get(k)])
                            graph[neighbours.get(j)][neighbours.get(k)] = graph[neighbours.get(k)][neighbours.get(j)] = true;
            visited[indexList[i]] = true;
        }
    }
    
    private void createCliques() {
        int[] nodeIndices = new int[n];
        boolean[] visited = new boolean[n];
        int[] neighbourCounts = new int[n + 1];
        int count, currentNode, maxCount;
        for (int i = 0; i < n; i++)
            visited[i] = false;
        currentNode = maxCount = 0;
        for (int i = 0; i < n; i++) {
            nodeIndices[i] = currentNode;
            visited[currentNode] = true;
            neighbourCounts[i] = maxCount;
            maxCount = 0;
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    count = 0;
                    for (int k = 0; k <= i; k++) {
                        if (graph[j][nodeIndices[k]])
                            count++;
                    }
                    if (maxCount <= count) {
                        currentNode = j;
                        maxCount = count;
                    }
                }
            }
        }
        neighbourCounts[n] = 0;
        cliques = new ArrayList<ArrayList<Integer>>();
        for (int i = n - 1; i >= 0; i--) {
            if (neighbourCounts[i] >= neighbourCounts[i + 1]) {
                cliques.add(new ArrayList<Integer>());
                cliques.get(cliques.size() - 1).add(nodeIndices[i]);
                for (int j = 0; j < i; j++)
                    if (graph[nodeIndices[i]][nodeIndices[j]])
                        cliques.get(cliques.size() - 1).add(nodeIndices[j]);
            }
        }
    }
    
    private void createJT() {
        boolean[] isPresent = new boolean[n];
        int cliqueSize, length;
        createCliques();
        /*System.out.println("Cliques");
        System.out.println(cliques.toString());*/
        length = cliques.size();
        junctionTree = new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < n; j++)
                isPresent[j] = false;
            cliqueSize = cliques.get(i).size();
            for (int j = 0; j < cliqueSize; j++)
                isPresent[cliques.get(i).get(j)] = true;
            junctionTree[i][i] = Integer.MIN_VALUE;
            for (int j = i + 1; j < length; j++) {
                junctionTree[i][j] = 0;
                cliqueSize = cliques.get(j).size();
                for (int k = 0; k < cliqueSize; k++)
                    if (isPresent[cliques.get(j).get(k)])
                        junctionTree[i][j]++;
                junctionTree[j][i] = junctionTree[i][j];
            }
        }
        /*System.out.println("Complete graph of cliques");
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                System.out.print(junctionTree[i][j] + " ");
            System.out.println();
        }*/
        Kruskal kruskal = new Kruskal(junctionTree);
        junctionTree = kruskal.mst();
        /*System.out.println("Clique Tree");
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                System.out.print(junctionTree[i][j] + " ");
            System.out.println();
        }*/
    }
    
    private void MAP() {
        ArrayList<Integer> ready = new ArrayList<Integer>();
        int assignmentLength, cliqueSize, degree, length, value;
        double assignmentPotential;
        length = junctionTree.length;
        for (int i = 0; i < length; i++) {
            degree = 0;
            for (int j = 0; j < length; j++)
                if (junctionTree[i][j] != 0)
                    degree++;
            if (degree == 1)
                ready.add(i);
        }
        /*System.out.println("Ready List");
        System.out.println(ready.toString());*/
        ArrayList<Integer> target = new ArrayList<Integer>();
        for (int i = 0; i < ready.size(); i++) {
            for (int j = 0; j < length; j++) {
                if (junctionTree[ready.get(i)][j] != 0) {
                    target.add(j);
                    break;
                }
            }
        }
        int[][] maxMessageIndex = new int[length][length];
        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++)
                maxMessageIndex[i][j] = -1;
        while (!ready.isEmpty()) {
            for (int i = 0; i < ready.size(); i++) {
                ArrayList<Integer> neighbourList = new ArrayList<Integer>();
                for (int j = 0; j < length; j++)
                    if ((junctionTree[ready.get(i)][j] != 0) && (target.get(i) != j))
                        neighbourList.add(j);
                ArrayList<Integer> currentMessageIndex = new ArrayList<Integer>();
                for (int j = 0; j < neighbourList.size(); j++)
                    currentMessageIndex.add(maxMessageIndex[neighbourList.get(j)][ready.get(i)]);
                ArrayList<Integer> currentClique = cliques.get(ready.get(i));
                cliqueSize = currentClique.size();
                assignmentLength = 1;
                for (int j = 0; j < cliqueSize; j++)
                    assignmentLength *= arity[currentClique.get(j)];
                HashMap<CliqueWrapper, Double> currentCliquePotential = new HashMap<CliqueWrapper, Double>();
                HashMap<CliqueWrapper, HashMap<Integer, Integer>> currentMaxAssignment = new HashMap<CliqueWrapper, HashMap<Integer, Integer>>();
                for (int j = 0; j < assignmentLength; j++) {
                    CliqueWrapper assignment = new CliqueWrapper(arity, currentClique);
                    value = j;
                    for (int k = cliqueSize - 1; k >= 0; k--) {
                        assignment.add(value % arity[currentClique.get(k)]);
                        value /= arity[currentClique.get(k)];
                    }
                    Collections.reverse(assignment);
                    HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
                    for (int k = 0; k < cliqueSize; k++)
                        nodeValue.put(currentClique.get(k), assignment.get(k));
                    assignmentPotential = cliquePotentials.get(ready.get(i)).get(assignment);
                    HashMap<Integer, Integer> currentAssignment = new HashMap<Integer, Integer>();
                    for (int k = 0; k < neighbourList.size(); k++) {
                        ArrayListWrapper separatorSet = new ArrayListWrapper();
                        separatorSet.addAll(separatorList.get(separatorIndex[ready.get(i)][neighbourList.get(k)]));
                        CliqueWrapper separatorAssignment = new CliqueWrapper(arity, separatorSet);
                        for (int l = 0; l < separatorSet.size(); l++)
                            separatorAssignment.add(nodeValue.get(separatorSet.get(l)));
                        assignmentPotential *= maxMessageList.get(currentMessageIndex.get(k)).get(separatorAssignment);
                        currentAssignment.putAll(maxMessageAssignment.get(currentMessageIndex.get(k)).get(separatorAssignment));
                    }
                    currentCliquePotential.put(assignment, assignmentPotential);
                    currentMaxAssignment.put(assignment, currentAssignment);
                }
                Iterator potentialIterator = currentCliquePotential.keySet().iterator();
                HashMap<CliqueWrapper, Double> messagePotential = new HashMap<CliqueWrapper, Double>();
                HashMap<CliqueWrapper, HashMap<Integer, Integer>> messageAssignment = new HashMap<CliqueWrapper, HashMap<Integer, Integer>>();
                ArrayList<Integer> messageSeparator = separatorList.get(separatorIndex[ready.get(i)][target.get(i)]);
                ArrayList<Integer> residualNodes = new ArrayList<Integer>();
                residualNodes.addAll(currentClique);
                residualNodes.removeAll(messageSeparator);
                while (potentialIterator.hasNext()) {
                    CliqueWrapper assignment = (CliqueWrapper)potentialIterator.next();
                    HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
                    for (int j = 0; j < cliqueSize; j++)
                        nodeValue.put(currentClique.get(j), assignment.get(j));
                    CliqueWrapper separatorAssignment = new CliqueWrapper(arity, messageSeparator);
                    for (int j = 0; j < messageSeparator.size(); j++)
                        separatorAssignment.add(nodeValue.get(messageSeparator.get(j)));
                    HashMap<Integer, Integer> residualAssignment = new HashMap<Integer, Integer>();
                    for (int j = 0; j < residualNodes.size(); j++)
                        residualAssignment.put(residualNodes.get(j), nodeValue.get(residualNodes.get(j)));
                    residualAssignment.putAll(currentMaxAssignment.get(assignment));
                    if (messagePotential.containsKey(separatorAssignment)) {
                        if (messagePotential.get(separatorAssignment) < currentCliquePotential.get(assignment)) {
                            messagePotential.put(separatorAssignment, currentCliquePotential.get(assignment));
                            messageAssignment.put(separatorAssignment, residualAssignment);
                        }
                    }
                    else {
                        messagePotential.put(separatorAssignment, currentCliquePotential.get(assignment));
                        messageAssignment.put(separatorAssignment, residualAssignment);
                    }
                }
                maxMessageList.add(messagePotential);
                maxMessageAssignment.add(messageAssignment);
                maxMessageIndex[ready.get(i)][target.get(i)] = maxMessageList.size() - 1;
            }
            ready.clear();
            target.clear();
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if ((junctionTree[i][j] != 0) && (maxMessageIndex[i][j] == -1)) {
                        boolean flag = true;
                        for (int k = 0; k < length; k++) {
                            if ((k != j) && (junctionTree[i][k] != 0)) {
                                if (maxMessageIndex[k][i] == -1) {
                                    flag = false;
                                    break;
                                }
                            }
                        }
                        if (flag) {
                            ready.add(i);
                            target.add(j);
                        }
                    }
                }
            }
        }
        /*System.out.println("Max Messages");
        for (int i = 0; i < maxMessageList.size(); i++) {
            System.out.println(i + " => ");
            Iterator messageIterator = maxMessageList.get(i).keySet().iterator();
            while (messageIterator.hasNext()) {
                CliqueWrapper assignment = (CliqueWrapper)messageIterator.next();
                System.out.println(assignment.toString() + " => " + maxMessageList.get(i).get(assignment));
            }
        }
        System.out.println("Max Message Assignments");
        for (int i = 0; i < maxMessageAssignment.size(); i++) {
            System.out.println(i + " => ");
            Iterator messageIterator = maxMessageAssignment.get(i).keySet().iterator();
            while (messageIterator.hasNext()) {
                CliqueWrapper assignment = (CliqueWrapper)messageIterator.next();
                System.out.println(assignment.toString() + " => ");
                Iterator assignmentIterator = maxMessageAssignment.get(i).get(assignment).keySet().iterator();
                while (assignmentIterator.hasNext()) {
                    Integer nodeValue = (Integer)assignmentIterator.next();
                    System.out.println(nodeValue + " => " + maxMessageAssignment.get(i).get(assignment).get(nodeValue));
                }
            }
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                System.out.print(maxMessageIndex[i][j] + " ");
            System.out.println();
        }*/
    }
    
    private void createAlpha() {
        HashMap<Integer, ArrayList<ArrayList<Integer>>> alpha = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();
        int cliqueSize, length, numCliques, numFactors, value;
        double currentPotential;
        numCliques = cliques.size();
        for (int i = 0; i < numCliques; i++) {
            ArrayList<ArrayList<Integer>> factors = new ArrayList<ArrayList<Integer>>();
            Iterator potentialsIterator = potentials.keySet().iterator();
            while (potentialsIterator.hasNext()) {
                ArrayList<Integer> arrayListKey = (ArrayList<Integer>)potentialsIterator.next();
                if (cliques.get(i).containsAll(arrayListKey))
                    factors.add(arrayListKey);
            }
            alpha.put(i, factors);
        }
        cliquePotentials = new HashMap<Integer, HashMap<CliqueWrapper, Double>>();
        for (int i = 0; i < numCliques; i++) {
            cliqueSize = cliques.get(i).size();
            length = 1;
            for (int j = 0; j < cliqueSize; j++)
                length *= arity[cliques.get(i).get(j)];
            HashMap<CliqueWrapper, Double> factorPotentials = new HashMap<CliqueWrapper, Double>();
            for (int j = 0; j < length; j++) {
                CliqueWrapper assignment = new CliqueWrapper(arity, cliques.get(i));
                value = j;
                for (int k = cliqueSize - 1; k >= 0; k--) {
                    assignment.add(value % arity[cliques.get(i).get(k)]);
                    value /= arity[cliques.get(i).get(k)];
                }
                Collections.reverse(assignment);
                HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
                for (int k = 0; k < cliqueSize; k++)
                    nodeValue.put(cliques.get(i).get(k), assignment.get(k));
                ArrayList<ArrayList<Integer>> factorList = alpha.get(i);
                numFactors = factorList.size();
                currentPotential = 1.0;
                for (int k = 0; k < numFactors; k++) {
                    CliqueWrapper factorAssignment = new CliqueWrapper(arity, factorList.get(k));
                    for (int l = 0; l < factorList.get(k).size(); l++)
                        factorAssignment.add(nodeValue.get(factorList.get(k).get(l)));
                    currentPotential *= potentials.get((ArrayListWrapper)factorList.get(k)).get(factorAssignment);
                }
                factorPotentials.put(assignment, currentPotential);
            }
            cliquePotentials.put(i, factorPotentials);
        }
        /*System.out.println("Clique Potentials");
        Iterator cliquePotentialsIterator = cliquePotentials.keySet().iterator();
        while (cliquePotentialsIterator.hasNext()) {            
            int key = (Integer)cliquePotentialsIterator.next();
            System.out.println(key + " => ");
            HashMap<CliqueWrapper, Double> potentialValue = (HashMap<CliqueWrapper, Double>)cliquePotentials.get(key);
            Iterator cliqueIterator = potentialValue.keySet().iterator();
            while (cliqueIterator.hasNext()) {
                CliqueWrapper cliqueKey = (CliqueWrapper)cliqueIterator.next();
                System.out.println(cliqueKey.toString() + " => " + (Double)potentialValue.get(cliqueKey));
            }
        }*/
    }
    
    private void computeMessages() {
        ArrayList<Integer> ready = new ArrayList<Integer>();
        int assignmentLength, cliqueSize, degree, length, value;
        double assignmentPotential;
        length = junctionTree.length;
        for (int i = 0; i < length; i++) {
            degree = 0;
            for (int j = 0; j < length; j++)
                if (junctionTree[i][j] != 0)
                    degree++;
            if (degree == 1)
                ready.add(i);
        }
        /*System.out.println("Ready List");
        System.out.println(ready.toString());*/
        separatorIndex = new int[length][length];
        for (int i = 0; i < length; i++) {
            separatorIndex[i][i] = -1;
            for (int j = i + 1; j < length; j++) {
                if (junctionTree[i][j] != 0) {
                    ArrayList<Integer> separators = new ArrayList<Integer>(cliques.get(i));
                    separators.retainAll(cliques.get(j));
                    separatorList.add(separators);
                    separatorIndex[i][j] = separatorIndex[j][i] = separatorList.size() - 1;
                }
                else
                    separatorIndex[i][j] = separatorIndex[j][i] = -1;
            }
        }
        /*System.out.println("Separators list");
        System.out.println(separatorList.toString());
        for (int i = 0; i < separatorIndex.length; i++) {
            for (int j = 0; j < separatorIndex.length; j++)
                System.out.print(separatorIndex[i][j] + " ");
            System.out.println();
        }*/
        ArrayList<Integer> target = new ArrayList<Integer>();
        for (int i = 0; i < ready.size(); i++) {
            for (int j = 0; j < length; j++) {
                if (junctionTree[ready.get(i)][j] != 0) {
                    target.add(j);
                    break;
                }
            }
        }
        messageIndex = new int[length][length];
        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++)
                messageIndex[i][j] = -1;
        while (!ready.isEmpty()) {
            for (int i = 0; i < ready.size(); i++) {
                ArrayList<Integer> neighbourList = new ArrayList<Integer>();
                for (int j = 0; j < length; j++)
                    if ((junctionTree[ready.get(i)][j] != 0) && (target.get(i) != j))
                        neighbourList.add(j);
                ArrayList<Integer> currentMessageIndex = new ArrayList<Integer>();
                for (int j = 0; j < neighbourList.size(); j++)
                    currentMessageIndex.add(messageIndex[neighbourList.get(j)][ready.get(i)]);
                ArrayList<Integer> currentClique = cliques.get(ready.get(i));
                cliqueSize = currentClique.size();
                assignmentLength = 1;
                for (int j = 0; j < cliqueSize; j++)
                    assignmentLength *= arity[currentClique.get(j)];
                HashMap<CliqueWrapper, Double> currentCliquePotential = new HashMap<CliqueWrapper, Double>();
                for (int j = 0; j < assignmentLength; j++) {
                    CliqueWrapper assignment = new CliqueWrapper(arity, currentClique);
                    value = j;
                    for (int k = cliqueSize - 1; k >= 0; k--) {
                        assignment.add(value % arity[currentClique.get(k)]);
                        value /= arity[currentClique.get(k)];
                    }
                    Collections.reverse(assignment);
                    HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
                    for (int k = 0; k < cliqueSize; k++)
                        nodeValue.put(currentClique.get(k), assignment.get(k));
                    assignmentPotential = cliquePotentials.get(ready.get(i)).get(assignment);
                    for (int k = 0; k < neighbourList.size(); k++) {
                        ArrayListWrapper separatorSet = new ArrayListWrapper();
                        separatorSet.addAll(separatorList.get(separatorIndex[ready.get(i)][neighbourList.get(k)]));
                        CliqueWrapper separatorAssignment = new CliqueWrapper(arity, separatorSet);
                        for (int l = 0; l < separatorSet.size(); l++)
                            separatorAssignment.add(nodeValue.get(separatorSet.get(l)));
                        assignmentPotential *= messageList.get(currentMessageIndex.get(k)).get(separatorAssignment);
                    }
                    currentCliquePotential.put(assignment, assignmentPotential);
                }
                Iterator potentialIterator = currentCliquePotential.keySet().iterator();
                HashMap<CliqueWrapper, Double> messagePotential = new HashMap<CliqueWrapper, Double>();
                ArrayList<Integer> messageSeparator = separatorList.get(separatorIndex[ready.get(i)][target.get(i)]);
                while (potentialIterator.hasNext()) {
                    CliqueWrapper assignment = (CliqueWrapper)potentialIterator.next();
                    HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
                    for (int j = 0; j < cliqueSize; j++)
                        nodeValue.put(currentClique.get(j), assignment.get(j));
                    CliqueWrapper separatorAssignment = new CliqueWrapper(arity, messageSeparator);
                    for (int j = 0; j < messageSeparator.size(); j++)
                        separatorAssignment.add(nodeValue.get(messageSeparator.get(j)));
                    if (messagePotential.containsKey(separatorAssignment))
                        messagePotential.put(separatorAssignment, messagePotential.get(separatorAssignment) + currentCliquePotential.get(assignment));
                    else
                        messagePotential.put(separatorAssignment, currentCliquePotential.get(assignment));
                }
                messageList.add(messagePotential);
                messageIndex[ready.get(i)][target.get(i)] = messageList.size() - 1;
            }
            ready.clear();
            target.clear();
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if ((junctionTree[i][j] != 0) && (messageIndex[i][j] == -1)) {
                        boolean flag = true;
                        for (int k = 0; k < length; k++) {
                            if ((k != j) && (junctionTree[i][k] != 0)) {
                                if (messageIndex[k][i] == -1) {
                                    flag = false;
                                    break;
                                }
                            }
                        }
                        if (flag) {
                            ready.add(i);
                            target.add(j);
                        }
                    }
                }
            }
        }
        /*System.out.println("Messages");
        for (int i = 0; i < messageList.size(); i++) {
            System.out.println(i + " => ");
            Iterator messageIterator = messageList.get(i).keySet().iterator();
            while (messageIterator.hasNext()) {
                CliqueWrapper assignment = (CliqueWrapper)messageIterator.next();
                System.out.println(assignment.toString() + " => " + messageList.get(i).get(assignment));
            }
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++)
                System.out.print(messageIndex[i][j] + " ");
            System.out.println();
        }*/
    }
    
    private void computeMax() {
        int assignmentLength, cliqueIndex, cliqueSize, value;
        double assignmentPotential, maxPotential;
        cliqueIndex = 0;
        ArrayList<Integer> neighbourList = new ArrayList<Integer>();
        for (int i = 0; i < messageIndex.length; i++)
            if (junctionTree[cliqueIndex][i] != 0)
                neighbourList.add(i);
        ArrayList<Integer> currentMessageIndex = new ArrayList<Integer>();
        for (int i = 0; i < neighbourList.size(); i++)
            currentMessageIndex.add(messageIndex[neighbourList.get(i)][cliqueIndex]);
        ArrayList<Integer> currentClique = cliques.get(cliqueIndex);
        cliqueSize = currentClique.size();
        assignmentLength = 1;
        for (int i = 0; i < cliqueSize; i++)
            assignmentLength *= arity[currentClique.get(i)];
        HashMap<CliqueWrapper, Double> currentCliquePotential = new HashMap<CliqueWrapper, Double>();
        for (int i = 0; i < assignmentLength; i++) {
            CliqueWrapper assignment = new CliqueWrapper(arity, currentClique);
            value = i;
            for (int j = cliqueSize - 1; j >= 0; j--) {
                assignment.add(value % arity[currentClique.get(j)]);
                value /= arity[currentClique.get(j)];
            }
            Collections.reverse(assignment);
            HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
            for (int j = 0; j < cliqueSize; j++)
                nodeValue.put(currentClique.get(j), assignment.get(j));
            assignmentPotential = cliquePotentials.get(cliqueIndex).get(assignment);
            for (int j = 0; j < neighbourList.size(); j++) {
                ArrayListWrapper separatorSet = new ArrayListWrapper();
                separatorSet.addAll(separatorList.get(separatorIndex[cliqueIndex][neighbourList.get(j)]));
                CliqueWrapper separatorAssignment = new CliqueWrapper(arity, separatorSet);
                for (int k = 0; k < separatorSet.size(); k++)
                    separatorAssignment.add(nodeValue.get(separatorSet.get(k)));
                assignmentPotential *= maxMessageList.get(currentMessageIndex.get(j)).get(separatorAssignment);
            }
            currentCliquePotential.put(assignment, assignmentPotential);
        }
        Iterator potentialIterator = currentCliquePotential.keySet().iterator();
        CliqueWrapper maxAssignment = null;
        maxPotential = -1.0;
        while (potentialIterator.hasNext()) {
            CliqueWrapper assignment = (CliqueWrapper)potentialIterator.next();
            if (maxPotential < currentCliquePotential.get(assignment)) {
                maxPotential = currentCliquePotential.get(assignment);
                maxAssignment = assignment;
            }
        }
        finalPotential = maxPotential;
        for (int i = 0; i < cliqueSize; i++)
            finalAssignment.put(currentClique.get(i), maxAssignment.get(i));
        for (int i = 0; i < neighbourList.size(); i++) {
            ArrayList<Integer> separatorSet = separatorList.get(separatorIndex[cliqueIndex][neighbourList.get(i)]);
            CliqueWrapper separatorAssignment = new CliqueWrapper(arity, separatorSet);
            for (int j = 0; j < separatorSet.size(); j++)
                separatorAssignment.add(finalAssignment.get(separatorSet.get(j)));
            finalAssignment.putAll(maxMessageAssignment.get(messageIndex[neighbourList.get(i)][cliqueIndex]).get(separatorAssignment));
        }
        /*System.out.println("Final Assignment");
        Iterator assignmentIterator = finalAssignment.keySet().iterator();
        while (assignmentIterator.hasNext()) {
            Integer nodeIndex = (Integer)assignmentIterator.next();
            System.out.println(nodeIndex + " => " + finalAssignment.get(nodeIndex));
        }*/
    }
    
    private void computeMarginals() {

    	int cliqueIndex;
        cliqueIndex = -1;
        for (int i = 0; i < cliques.size(); i++) {
            if (cliques.get(i).containsAll(variables)) {
                cliqueIndex = i;
                break;
            }
        }
        if (cliqueIndex == -1) {
            System.err.println("Either variables are spanning more than one clique or input is invalid");
            return;
        }
        
        ArrayList<Integer> neighbourList = new ArrayList<Integer>();
        int assignmentLength, cliqueSize, value;
        double assignmentPotential;
        for (int i = 0; i < messageIndex.length; i++)
            if (junctionTree[cliqueIndex][i] != 0)
                neighbourList.add(i);
        ArrayList<Integer> currentMessageIndex = new ArrayList<Integer>();
        for (int i = 0; i < neighbourList.size(); i++)
            currentMessageIndex.add(messageIndex[neighbourList.get(i)][cliqueIndex]);
        ArrayList<Integer> currentClique = cliques.get(cliqueIndex);
        cliqueSize = currentClique.size();
        assignmentLength = 1;
        for (int i = 0; i < cliqueSize; i++)
            assignmentLength *= arity[currentClique.get(i)];
        HashMap<CliqueWrapper, Double> currentCliquePotential = new HashMap<CliqueWrapper, Double>();
        for (int i = 0; i < assignmentLength; i++) {
            CliqueWrapper assignment = new CliqueWrapper(arity, currentClique);
            value = i;
            for (int j = cliqueSize - 1; j >= 0; j--) {
                assignment.add(value % arity[currentClique.get(j)]);
                value /= arity[currentClique.get(j)];
            }
            Collections.reverse(assignment);
            HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
            for (int j = 0; j < cliqueSize; j++)
                nodeValue.put(currentClique.get(j), assignment.get(j));
            assignmentPotential = cliquePotentials.get(cliqueIndex).get(assignment);
            for (int j = 0; j < neighbourList.size(); j++) {
                ArrayListWrapper separatorSet = new ArrayListWrapper();
                separatorSet.addAll(separatorList.get(separatorIndex[cliqueIndex][neighbourList.get(j)]));
                CliqueWrapper separatorAssignment = new CliqueWrapper(arity, separatorSet);
                for (int k = 0; k < separatorSet.size(); k++)
                    separatorAssignment.add(nodeValue.get(separatorSet.get(k)));
                assignmentPotential *= messageList.get(currentMessageIndex.get(j)).get(separatorAssignment);
            }
            currentCliquePotential.put(assignment, assignmentPotential);
        }
        Iterator potentialIterator = currentCliquePotential.keySet().iterator();
        while (potentialIterator.hasNext()) {
            CliqueWrapper assignment = (CliqueWrapper)potentialIterator.next();
            HashMap<Integer, Integer> nodeValue = new HashMap<Integer, Integer>();
            for (int i = 0; i < cliqueSize; i++)
                nodeValue.put(currentClique.get(i), assignment.get(i));
            CliqueWrapper variableAssignment = new CliqueWrapper(arity, variables);
            for (int i = 0; i < variables.size(); i++)
                variableAssignment.add(nodeValue.get(variables.get(i)));
            if (marginal.containsKey(variableAssignment))
                marginal.put(variableAssignment, marginal.get(variableAssignment) + currentCliquePotential.get(assignment));
            else
                marginal.put(variableAssignment, currentCliquePotential.get(assignment));
        }
    }
    
    
    public Double getOutput(ArrayList<Integer> listVar, ArrayList<Integer> listVal ) {
    	variables = listVar;
    	computeMarginals();
    	
        Double potentialSum = 0.0 ,res =0.0;

        Iterator marginalIterator = marginal.keySet().iterator();
        while (marginalIterator.hasNext()) {
            CliqueWrapper key = (CliqueWrapper)marginalIterator.next();
            potentialSum += marginal.get(key);
        }
        
        marginalIterator = marginal.keySet().iterator();
        while (marginalIterator.hasNext()) {
            CliqueWrapper key = (CliqueWrapper)marginalIterator.next();
            List<Integer> keyList = key;
            if(isListSame(keyList, listVal))
            	return (marginal.get(key) / potentialSum);
        }
        
        return -1.0;
    }
    
	public static Boolean isListSame(List<Integer> A,List<Integer> B){
		if (A.size() != B.size())
			return false;
		for(Integer i=0;i<A.size();i++){
			if( A.get(i) != B.get(i)){
				return false;
			}
		}		
		return true;
	}

}
